package site.wanjiahao;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * 最长公共子串
 */
public class LCSSubstring {

    public static void main(String[] args) {
        String str1 = "ABCBA";
        String str2 = "BABCA";
        System.out.println(lcs(str1, str2));
    }

    public static int lcs(String str1, String str2) {
        if (str1.length() == 0 || str2.length() == 0) return 0;
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        char[] rowEle = char1, colEle = char2;
        if (char1.length < char2.length) {
            rowEle = char2;
            colEle = char1;
        }
        int[] dp = new int[colEle.length + 1];
        int max = 0;
        for (int row = 1; row <= rowEle.length; row++) {
            // 逆序遍历
            for (int col = colEle.length; col >= 1; col--) {
                if (char1[row - 1] == char2[col - 1]) {
                    dp[col] = dp[col - 1] + 1;
                } else {
                    dp[col] = 0;
                }
                max = Math.max(dp[col], max);
            }
        }
        return max;
    }

    // 一维数组实现
    public static int lc2(String str1, String str2) {
        if (str1.length() == 0 || str2.length() == 0) return 0;
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        char[] rowEle = char1, colEle = char2;
        if (char1.length < char2.length) {
            rowEle = char2;
            colEle = char1;
        }
        int[] dp = new int[colEle.length + 1];
        int max = 0;
        for (int row = 1; row <= rowEle.length; row++) {
            // 保存斜对角值
            int cur = 0;
            for (int col = 1; col <= colEle.length; col++) {
                int leftTop = cur;
                cur = dp[col];
                if (char1[row - 1] == char2[col - 1]) {
                    dp[col] = leftTop + 1;
                } else {
                    dp[col] = 0;
                }
                max = Math.max(dp[col], max);
            }
        }
        return max;
    }

    // 动态规划
    public static int lcs1(String str1, String str2) {
        if (str1.length() == 0 || str2.length() == 0) return 0;
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
        int[][] dp = new int[char1.length + 1][char2.length + 1];
        int max = 0;
        for (int row = 1; row <= char1.length; row++) {
            for (int col = 1; col <= char2.length; col++) {
                if (char1[row - 1] == char2[col - 1]) {
                    dp[row][col] = dp[row - 1][col - 1] + 1;
                }
                max = Math.max(dp[row][col], max);
            }
        }
        return max;
    }


}
